# 打家劫舍

def rob(nums: list[int])->int:
        
        if len(nums) == 0:
            return 0
        N = len(nums)
        dp = [0]*(N+1)
        dp[0] = 0
        dp[1] = nums[0]
        for k in range(2,N+1):
            dp[k] = max(dp[k-1],nums[k-1]+dp[k-2])
        return dp[N]

# 优化后：
def rob(nums):
    if len(nums) == 0:
        return 0
    prev2 = 0  # 代表 dp[i - 2]
    prev1 = nums[0]  # 代表 dp[i - 1]
    for i in range(1, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = curr
    return prev1

#参考：nettee

# 打家劫舍

def rob(nums: list[int])->int:
    if len(nums) == 0:
        return 0
    N = len(nums)
    dp = [0]*(N+1)
    dp[0] = 0
    dp[1] = nums[0]
    for k in range(2,N+1):
        dp[k] = max(dp[k-1],nums[k-1]+dp[k-2])
    return dp[N]

# 优化后：
def rob_optimized(nums):
    if len(nums) == 0:
        return 0
    prev2 = 0  # 代表 dp[i - 2]
    prev1 = nums[0]  # 代表 dp[i - 1]
    for i in range(1, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = curr
    return prev1

# 示例使用
houses_money = [1, 2, 3, 1, 6, 5]
result1 = rob(houses_money)
result2 = rob_optimized(houses_money)

print(f"使用动态规划数组方法，抢劫到的最大金额是: {result1}")
print(f"使用优化后方法，抢劫到的最大金额是: {result2}")